package queue.homework;


import java.util.LinkedList;
import java.util.Queue;

/**
 * 使用队列实现栈
 * 栈 从一端进，从一端出
 * 队列，从一端进，从另一端出
 * 入栈等同于入队
 * <p>
 * 出栈等同于取出队列队尾元素
 * 使用队列2存放队列1队尾元素之前的元素
 * 队列1 全部出队，前n-1个元素在队列2 入队，
 * 改变引用
 */
class MyStack {

    private Queue<Integer> q;


    /**
     * Initialize your data structure here.
     * O（1）
     */
    public MyStack() {
        q = new LinkedList<>();

    }

    /**
     * 对于一个栈来说，关键是栈顶在哪里。
     * <p>
     * 栈是一端入，同一端出；而队列是一段入，另一端出。如果只给一个队列，我们先假设，入队的一端是栈顶。
     * <p>
     * 一旦这样定义，那么，我们封装的这个MyStack的入栈操作就很简单：直接把元素入队即可
     * O（1）
     *
     * @param x
     */
    public void push(int x) {
        q.add(x);
    }


    /**
     * 出栈：即拿到队尾的那个元素
     * <p>
     * 因为此时，我们只能取出队首的元素，所以，要想拿到队尾的元素，我们就必须先把现在在队列中的n-1个元素都取出来。剩下的哪一个元素，就是队尾
     * 的元素。
     * <p>
     * 可是，取出的n-1个元素 我们不能扔掉，问题又限制我们必须使用队列这种数据结构，所以，此时，我们可以使用另外的一个队列q2，来存储从q中出队的
     * 前n-1个元素。最后，q里只剩下一个元素，这个元素就是我们要拿出的“栈顶元素”。将这个元素出队（删除后），q2里面的数据就是原始的数据，我们用q2覆盖
     * q就好
     * O(n)
     *
     * @return
     */
    public int pop() {
        //创建另外一个队列q2
        Queue<Integer> q2 = new LinkedList<>();
        //除了最后一个元素，将q中的所有元素放入q2
        while (q.size() > 1) {
            q2.add(q.remove());
        }
        //q中剩下的最后一个元素就是 “栈顶” 元素
        int result = q.remove();
        //此时q2存储整个数据结构存储的所有其他数据，赋值给q
        q = q2;
        //返回栈顶元素
        return result;
    }

    /**
     * 一旦我们实现了 pop ,实现top就简单了。我们可以复用我们已经实现的pop，将栈顶元素拿出来，记录下来，作为返回值。然后因为top不会删除元素，
     * 我们再将这个值入栈即可
     * <p>
     * O(n)
     *
     * @return
     */
    public int top() {
        //先取出栈顶元素，然后再入栈
        int ret = pop();
        push(ret);
        return ret;
    }

    /**
     * O(1)
     * @return
     */
    public boolean empty() {
        return q.isEmpty();
    }

    /**
     * O（1）
     * @return
     */
    public int getSize() {
        return q.size();
    }
}
